\section{Metaheur\'istica GRASP}
\label{sec::grasp}

\subsection{Algoritmo y correctitud}

Por \'ultimo, implementamos un algoritmo basado en la metaheur\'istica
GRASP (Greedy Randomized Adaptable Search Procedures) como esta 
descripta en ~\cite{grasp}.

El algoritmo realiza una serie de iteraciones que se descompone en
dos partes: La primera consiste en obtener un candidado a soluci\'on
mediante una heur\'istica constructiva golosa basada en un algoritmo
con un componente randomizado. La segunda consiste en mejorar este 
candidato mediante un procedimiento de b\'usqueda local. El algoritmo
y sus dos partes separadas se encuentran detalladas en el algoritmo
~\ref{algo::graspabs}.

\begin{algorithm}[H] 
	\caption{Pseudoc\'odigo para la metaheur\'istica GRASP (Greedy
	Adaptative Randomized Search Procedure) en su versi\'on m\'as general. }
	\label{algo::graspabs}
	\begin{algorithmic}
		\Function{grasp}{$G = (V,E), C \subseteq V$ comp. conexa}
			\State $Mejor \gets C$
			\While{$\neq criterioParada$}
				\State $S \gets greedyRandomizado(G,C,\alpha)$
				\State $S \gets local(G,C,S)$
				\If{$S$ es mejor que $Mejor$}
					\State $Mejor \gets S$
				\EndIf
			\EndWhile
			\Return $Mejor$
		\EndFunction
	\end{algorithmic}
\end{algorithm}

La primer parte del algoritmo consiste en aplicar una heur\'istica
golosa similar a la presentada en la secci\'on~\ref{sec::greedy}. La
diferencia en este caso es que en vez de obtener determin\'isticamente
un candidato a soluci\'on (por ejemplo, en el algoritmo goloso 
presentado el mismo se obten\'ia encontrando el nodo de mayor cantidad
de vecinos (incluyendo posiblemente si mismo) sin dominar), lo que se
hace es ordenar los candidatos seg\'un un criterio y tomar un candidato
al azar dentro de un rango restrigindo de los mismos. Esta lista acotada
se conoce como RCL (\textit{Restricted Candidate List} o \textit{Lista
Restringida de Candidato}). Luego se repite el mismo procedimiento hasta
que se tiene un conjunto dominante. Este procedimiento a grandes rasgos
se puede ver en el algoritmo~\ref{algo::graspabs}.

En nuestro caso, utilizamos un ordenamiento basado nuevamente en la 
cantidad de nodos dentro de la vecindad cerrada del nodo que no est\'an
dominados. Para ello, en vez de simplemente iterar e irnos quedando con
el mejor, lo que hicimos fue ir insertando los nodos en una cola de 
prioridad implementada mediante un \textit{max-heap}, con el \'orden
presentado anteriormente.

Para determinar el tama\~no de la RCL se utiliza una un porcentaje $K$
entero entre 0 y 100. Luego, para tomar un valor al azar entre los 
primeros $K \%$ nodos de la componente de acuerdo al ordenamiento 
presentado anteriormente, tomamos un valor entero $i$ (al azar) entre $0$ y
$\frac{Kn}{100}$. Luego iterativamente vamos removiendo el elemento
tope de la cola de prioridad hasta llegar al $i$-\'esimo nodo. Este es
el nodo que elegimos en esta iteraci\'on, actualizamos (de manera 
id\'entica a como realizamos para la iteraci\'on del algoritmo goloso
constructivo) y repetimos hasta que obtengamos un conjunto dominante.
Esta parte del algoritmo se describe en profundidad en el algoritmo
~\ref{algo::graspGreedy}.

\begin{algorithm}[H] 
	\caption{Pseudoc\'odigo para la heur\'istica golosa constructiva 
	randomizada usada como primer paso para cada iteraci\'on del 
	algortimo GRASP. }
	\label{algo::graspGreedy}
	\begin{algorithmic}
		\Function{greedyRandomizado}{$G = (V,E), C \subseteq V$ comp. conexa, $\alpha$ porcentaje}
			\State $D \gets \{ \}$
			\While{$D$ no domina $C$}
				\State $orden \gets max-heap()$
				\ForAll{$v \in C \backslash D $}
					\State $encolar(orden, (N[v],v))$
				\EndFor
				\State $k \gets \lfloor \frac{\alpha |C|}{100} \rfloor$
				\State \Var $elegido$
				\State \Var $remover \gets azar([0 \dots, k])$
				\While{$remover > 0$}
					\State $elegido \gets desencolar(orden)$
					\State $remover \gets remover - 1$
				\EndWhile
				\State $D \gets D \bigcup \{ elegido \}$
			\EndWhile
		\EndFunction
	\end{algorithmic}
\end{algorithm}


La segunda parte del algoritmo consiste en mejorar la soluci\'on 
devuelta por el algoritmo goloso randomizado. Para ello usamos la misma
b\'usqueda local que implementamos anteriormente, excepto que en vez
de utilizar toda la componente como nuestra soluci\'on inicial, usamos
las soluci\'on devuelta por el algoritmo goloso constructivo randomizado.

En cada iteraci\'on entonces generamos una soluci\'on nueva mediante
estos dos procedimientos. El resultado final devuelto por el m\'etodo
GRASP es la mejor de todas las soluciones encontradas en todas las 
iteraciones.

Al igual que para el caso de la b\'squeda local analizado en la secci\'on
~\ref{sec::local}, es necesario definir varios par\'ametros del
algoritmo. Algunos de ellos, al ser parte de la b\'usqueda local misma
(que reutilizamos para la implementaci\'on de GRASP). Otros sin embargo
no dependen de ella.

Los par\'ametros analizados son:

\begin{itemize}
	\item \textbf{Criterio de parada: } Nuevamente elegimos como 
	criterio de parada cantidad de iteraciones sin mejorar la soluci\'on
	m\'inima alcanzada hasta el momento.
	\item \textbf{Lista de candidatos: } Para elegir la lista de 
	candidatos utilizamos un porcentaje como par\'ametro del algoritmo
	GRASP, el cual usamos para tomar un subconjunto de los nodos 
	posibles en cada paso de la elecci\'on de la heur\'istica golosa
	randomizada.
	\item \textbf{Criterio de parada de la b\'usqueda local: } Al
	utilizar el mismo m\'etodo de b\'usqueda local explicado en la
	secci\'on~\ref{sec::local}, se utiliza el mismo criterio de parada.
	Sin embargo, permitimos que se pueda alterar el par\'ametro de la
	cantidad de iteraciones especificamente para el algoritmo grasp. 
\end{itemize}

Este algoritmo, al igual que los tres anteriores presentados, es una
heur\'istica. Sin embargo, es dif\'icil encontrar un caso particular 
donde esta metaheur\'istica falle dado su comportamiento no aleatorio.

En el an\'alisis te\'orico posterior del algoritmo (de manera similar a como 
realizamos en la secci\'on~\ref{sec::local}), no haremos un an\'alisis
sobre el balance costo-beneficio de estos par\'ametros del algoritmo 
(es decir los supondr\'emos como dados). Posteriormente realizaremos un
an\'alisis m\'as fino.

\subsection{Implementaci\'on en C++ y complejidad}

En primer lugar estudiemos la implementaci\'on de la nueva funci\'on
\texttt{greedyRandomizado}, la primer parte de la metaheur\'istica
GRASP.

La implementaci\'on en C++ sigue los lineamientos presentados en los 
algoritmos~\ref{algo::graspabs} y~\ref{algo::graspGreedy}. 

Para la implementaci\'on de una cola de prioridad utilizamos el tipo
\texttt{vector} de \texttt{pair<int,int>}, junto con los m\'etodos
\texttt{make\_heap} y \texttt{pop\_heap}. 

El uso de \texttt{pair<int, int>} como tipo del \texttt{vector} 
esta motivado en la manera en que C++ maneja el
\'orden de las tuplas de enteros: Se compara por primer coordenada y
en caso de empate se desempata por segunda. Poniendo entonces en el
primer elemento de la tupla, la cantidad de vecinos sin dominar del 
nodo (para lo cual utilizamos nuevamente la funci\'on 
\texttt{queDominaria} que implementamos para el algoritmo heur\'istico
goloso), pod\'iamos ordenar muy f\'acilmente los nodos por cantidad de
vecinos sin cubrir.

La raz\'on del uso de un \texttt{vector} en vez del tipo 
\texttt{priority\_queue} de C++ se debe a dos motivos:

\begin{itemize}
	\item Al poder declarar el tama\~no del vector al instanciarlo,
	evitamos las constantes asociadas a tener que agrandar una 
	estructura de datos al agregarle m\'as cosas.
	\item La funci\'on \texttt{make\_heap} se implementa mediante
	el algoritmo de Floyd que tiene complejidad lineal~\cite{cppmh}.
	Por lo tanto, nos ahorramos un costo logar\'itmico que vendr\'ia
	asociado a las inserciones a realizar a la estructura 
	\texttt{priority\_queue}.
\end{itemize}

Y para desencolar elementos del vector, usamos la funci\'on 
\texttt{pop\_heap}, que tiene complejidad $O(\log n)$ con $n$ la 
cantidad de elementos en la cola~\cite{cppph}.

Para hacer la elecci\'on al azar utilizamos el generador de n\'umeros
aleatorios que es parte de la librer\'ia estandar de C++, \texttt{rand}.
Inicializamos el mismo usando \texttt{srand}, y como semilla utilizamos
la hora actual (en segundos) devuelta por la funci\'on de la librer\'ia
estandar \texttt{time} de C++.

El resto de los detalles implementativos son completamente an\'alogos a
los presentados para el algoritmo goloso constructivo que tratamos en la
secci\'on~\ref{sec::greedy}.

La implementaci\'on de la funci\'on que realiza efectivamente el ciclo
de GRASP es muy similar a la presentada en el algoritmo
~\ref{algo::graspabs}. Para implementar el criterio de parada de 
iteraciones entre mejoras, utilizamos un procedimiento similar al usado
para implementar el algoritmo~\ref{algo::local}.

Para analizar la complejidad del algoritmo, primero analizaremos la
complejidad del algoritmo goloso constructivo randomizado. 

Al ser este muy similar al algoritmo goloso constructivo presentado 
anteriormente, no haremos hincapi\'e en la complejidad de las funciones
com\'unes a ambos. 

Observemos primero que nada que, gracias al uso de la funci\'on
\texttt{make\_heap}, que es lineal por utilizar el algoritmo de 
heapificaci\'on de Floyd, el costo computacional en tiempo sigue siendo
$O(n)$~\cite{cppmh} para esta parte, igual que el requerido para la b\'usqueda del
m\'inimo que utilizamos en el algoritmo goloso de la secci\'on
~\ref{sec::greedy}.

El impacto adicional en este m\'etodo esta entonces en obtener el 
$k$-\'esimo elemento. Puesto que en peor caso necesitamos hacer una
cantidad $n-1$ de extracciones (mediante la funci\'on 
\texttt{pop\_heap}). Siendo la complejidad de esta operaci\'on
$O(\log n)$ por haber como m\'aximo $n$ elementos en todo momento 
en la cola de prioridad~\cite{cppph}, tenemos un total de $O(n \log n)$
costo. El ciclo principal pasa a ser $O(m + n \log n)$ en vez de 
$O(m + n)$ como antes, y por lo tanto la complejidad total del algoritmo
goloso randomizado es $O(n \cdot (m + n \log n)) = O(nm + n^2 \log n)$. 

Para la complejidad final del algoritmo entonces, observemos que el 
cuerpo del ciclo principal de la funci\'on \texttt{grasp} propiamente
dicha realiza un llamado a \texttt{golosoRandomizado} y otra a 
\texttt{local}. La primera tiene complejidad $O(nm + n^2 \log n)$, y
la segunda tiene costo $O(n^3c + n^2 m)$ con $c$ la cantidad de 
iteraciones de la b\'usqueda local. Finalmente, el costo de 
actualizar es $O(n)$ puesto que tenemos que copiar al m\'inimo cada
vez que actualizamos.

Del mismo modo en que realizamos en el an\'alisis de la secci\'on 
\texttt{sec::greedy}, si $cg$ es la cantidad de iteraciones m\'aximas
de par\'ametro del GRASP, tenemos que el cuerpo interno del ciclo se
ejecutar\'a un m\'aximo de $O(cg \cdot n)$ veces. En total entonces,
el costo puede ser acotado por $O((cg \cdot n) \cdot (nm + n^2 \log n 
+ n^3c + n^2 m + n )$.
